package demo;

class MyLinkedList {

    private class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    private ListNode head;
    private int size;
    private ListNode tail;
//    private ListNode dummyHead;

    public MyLinkedList() {
        head = new ListNode(0);
        size = 0;
        tail = new ListNode(0);
        head.next = tail;
        tail.next = null;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode cur = head;
        for (int i = 0; i <= index; i++) {
            cur = cur.next;
            if (cur == null) {
                return -1;
            }
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        ListNode newNode = new ListNode(val);
        // 新节点的下一个结点为head.next
        newNode.next = head.next;
        // head的next为newNode
        head.next = newNode;
        size++;
    }

    public void addAtTail(int val) {
        tail.val = val;
        tail.next = new ListNode(0);
        tail = tail.next;
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) {
            return;
        }
        if (index == 0) {
            addAtHead(val);
            return;
        }
        if (index == size) {
            addAtTail(val);
            return;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = cur.next;
        cur.next = newNode;
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        size--;
    }

    public void print() {
        ListNode cur = head.next;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int index = 0;
        int val = 10;
        MyLinkedList obj = new MyLinkedList();
        int param_1 = obj.get(index);
        obj.addAtHead(1);
        obj.print();
        obj.addAtTail(3);
        obj.print();
        obj.addAtIndex(1, 2);
        System.out.println("新增atIndex");
        obj.print();
        System.out.println(obj.get(1));
        obj.deleteAtIndex(1);
        obj.print();
        System.out.println(obj.get(0));
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */